package List;

/**
 * 206反转链表
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 */
public class reverseList {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 双指针
     * pre--->cur--->temp
     * null  head  cur.next
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    /**
     * 递归
     * @param head
     * @return
     */
    public ListNode reverseList2(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一个节点
        cur.next = prev;// 反转
        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        return reverse(cur, temp);
    }

    /**
     * hot100一刷
     * hot100二刷
     */
    class Solution {
        public ListNode reverseList(ListNode head) {
            ListNode pre = null;
            ListNode cur = head;
            ListNode post;
            while (cur != null) {
                post = cur.next;
                cur.next = pre;
                pre = cur;
                cur = post;
            }
            return pre;
        }

        public ListNode reverseList2(ListNode head) {
            return reverse(null, head);
        }

        public ListNode reverse(ListNode pre, ListNode cur) {
            if (cur == null)
                return pre;
            ListNode temp = cur.next;
            cur.next = pre;

            return reverse(cur, temp);
        }

    }
}
